package string.compare;

import java.util.Arrays;

/**
 * @Classname : LongestSubstringWithoutRepeatingCharacters
 * @Description : 3. 无重复字符的最长子串
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 * @Author : chentianyu
 * @Date 2022/12/18 23:22
 */


public class LongestSubstringWithoutRepeatingCharacters {
    public int lengthOfLongestSubstring(String s) {
        // 映射表记录各个字符最近出现的位置
        int[] table = new int[128];
        // 避免与双指针处于位置0产生歧义，将默认值初始化为0
        Arrays.fill(table, -1);
        int max = 0, l = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            // 当前字符出现过 且 出现位置大于等于左指针，则左指针移动到当前字符出现位置的下一位
            if (table[c] >= l) l = table[c] + 1;
                // 左指针移动会缩小长度，当左指针不移动时更新最大长度
            else max = Math.max(max, r - l + 1);
            // 更新当前字符出现的位置
            table[c] = r;
        }
        return max;
    }
}
